6장. 자료구조·복잡도

AI 엔지니어링 선수지식 — 6장. 대상: 고등학생·학부 1년차.

6. 자료구조·복잡도

LLM 은 왜 컨텍스트가 길면 느려지나, 왜 KV cache 가 필요한가 — 이 답이 자료구조·복잡도에 있습니다. EP5 의 KV cache 와 어텐션 비용을 이해하는 열쇠입니다.

6.1 시간복잡도 Big-O

데이터가 N개로 늘 때 시간이 얼마나 빨리 늘어나는가의 표기입니다.

비유 — 친구 만나기. O(1)은 단톡방 공지(인원 무관 한 번), O(N)은 한 명씩 전화(100명=100통), O(N²)은 모두가 모두와 1:1 만남(100명=약 10,000번)입니다.

직접 해보기 — N=100 이면 O(N)=100, O(N²)=10,000(100배 차이!), O(log N)≈7(가장 빠름)입니다. 리스트 검색 in 은 O(N)이지만 집합(set)은 O(1)입니다.

s = set(range(1000000))
print(500000 in s)   # 거의 즉시 (해시 O(1))

실무. "이 코드 왜 느리지?" 의 답이 대부분 복잡도이며, O(N²)를 O(N log N)으로 바꾸는 것이 최적화의 핵심입니다.

LLM 연결. 어텐션은 O(N²)입니다. 모든 단어가 모든 단어와 내적(1.3)하기 때문에, 컨텍스트가 2배면 비용이 4배가 됩니다. EP5·EP6 의 효율화 연구가 이 N² 를 줄이려는 시도입니다.

더 깊이 — Khan Academy Algorithms

6.2 해시·트리·큐

데이터를 빠르게 찾고(해시) 정렬하고(트리) 순서를 관리하는(큐) 그릇들입니다.

비유. 해시테이블은 사물함(번호 알면 즉시 꺼냄 O(1)), 트리는 토너먼트 대진표(단계적 탐색 O(log N)), 큐는 줄 서기(먼저 온 게 먼저, FIFO)입니다.

직접 해보기 — 딕셔너리(해시)로 단어를 세면 count[w] = count.get(w, 0) + 1 한 줄로 {'고양이': 3, '개': 2} 처럼 즉시 집계됩니다.

phone = {"철수": "010-1", "영희": "010-2"}
print(phone["영희"])   # 즉시 (해시 O(1))

실무. 토크나이저(단어↔숫자 매핑)가 해시이고, 캐시·중복 제거에 set/dict 가 필수입니다.

LLM 연결. 토크나이저의 어휘 사전이 해시테이블입니다(단어 → ID 즉시 변환). 섹션 7 과 연결됩니다.

더 깊이 — Khan Academy CS

6.3 KV Cache

이미 계산한 단어들의 결과를 저장해 두고 재사용하는 것입니다(O(N²) 부담 완화).

비유 — 책갈피. 읽은 페이지를 매번 처음부터 다시 펴면 O(N²)지만, 책갈피(cache)로 이전 계산을 보관하면 새 단어만 계산하면 됩니다.

직접 해보기 — 캐시 없이 단어 100개를 생성하면 1+2+...+100 = 5050번(O(N²))이지만, KV cache 로 이전 99개를 재사용하면 매번 1번씩 100번(O(N))으로 줄어듭니다.

cache = {}
def fib(n):
    if n < 2: return n
    if n in cache: return cache[n]   # 재사용
    cache[n] = fib(n-1) + fib(n-2); return cache[n]
print(fib(50))   # 캐시 없으면 수십 초, 있으면 즉시

실무. LLM 추론 속도의 핵심으로, KV cache 없이는 긴 대화가 기하급수적으로 느려집니다. GPU 메모리의 큰 부분을 차지하죠.

LLM 연결. EP5 의 KV cache 가 바로 이것으로, 어텐션 O(N²)의 반복 계산을 저장으로 줄입니다.

더 깊이 — Jay Alammar: Illustrated Transformer

6.4 정리

한 문장으로, 어텐션은 모두가 모두를 보는 O(N²)라 느리고, 그걸 KV cache(저장 재사용)로 완화하는 것이 LLM 서빙의 핵심입니다.

참고 자료 — Khan Academy CS · Jay Alammar Illustrated Transformer